1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n,m;
double w[999];
double x[999],y[999];
double dis[999][999];
void floy()//floyed
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&i!=k&&j!=k)
{
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
//int x,y;
scanf("%lf%lf",&x[i],&y[i]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
char c;
cin>>c;
if(c=='1')
{
double xx=(x[i]-x[j]),yy=y[i]-y[j];
dis[i][j]=sqrt(xx*xx+yy*yy);
}
else dis[i][j]=99999999;
}//联通求距离
floy();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][j]<99999999&&w[i]<dis[i][j])
{
w[i]=dis[i][j];//找最大值
}
double maxf=99999999;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j&&dis[i][j]>=99999999)
{
double xx=(x[i]-x[j]),yy=y[i]-y[j];
maxf=min(maxf,w[i]+w[j]+sqrt(xx*xx+yy*yy));//添边找最小
}
}
for(int i=1;i<=n;i++) maxf=max(maxf,w[i]);//找最大
printf("%.6lf",maxf);
return 0;
}
|
